你一共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须有 k 枚硬币。
给定一个数字 n ,找出可形成完整阶梯行的总行数。
n 是一个非负整数,并且在32位有符号整形范围内。
示例:
① n=5
硬币排列成:
●
● ●
● ●
因为第三行不完整,所以 return 2 .
② n=8
硬币的排列为:
●
● ●
● ● ●
● ●
所以返回值为 3.
code:
var arrangeCoins = function(n) {
let k =0;
while (n>0) {
k++;
n=n-k;
}
return n === 0? k:k-1;
};
执行测试后发现是没问题的。
这一种办法就是暴力破解法,思路是这样的:
设置 k 为行数,循环n ,直到n 小于或者等于0 为之,
每次循环k+1,同时 n-k(因为行数=硬币数),
最后看n是否为0,如果是刚刚好,返回k,如果不是0,即最后一行是失效的,所以返回k-1.
但是我们还可以用二分查找法来实现这个算法.
涉及知识点
用Math的方法(我在前面的面试题目中,有介绍过,可以看一下).
然后我们需要掺杂数学知识:
计算第k行的结果公式为 : k*(k+1) /2
code:
var arrangeCoins =function {
if (!n) {
return 0;
}
let sum = n*2
let left = 0;
let right = n;
while(n) {
let middle = Math.round((left+right)/2);
if(middle *(middle+1) ===sum) {
return middle;
} else if (middle * (middle+1) < sum) {
left= middle;
} else {
right=middle;
}
if(left=== right-1) {
return left;
}
}
};
以上,就是二分法查找的方法求解。
那么,我前面提到的不用 + - 的符号可以做到两个整数的和是如何做到的呢, 下面 ,就让我们来看一下吧。
涉及知识点 : 异或
这个知识点是不能很快的了解,所以希望大家可以自己去搜索资料,我就直接贴code了
var getSum = function(a,b) {
if (a === 0 ) return b;
if (b === 0) return a;
return getSum(a^b,(a&b) <<1);
}
代數解法
function fibonacci(n) {
return Math.round(
(Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) * (Math.sqrt(5) / 5)
)
}
不使用加減號實現加減法
https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators#(%E4%BD%8D%E5%85%83_XOR)
本科系應該都知道二進位加法只需透過AND XOR即可實現
AND結果是進位數 因此使用 << 1 位移進位
XOR結果是未含進位結果
最後再把未含進位結果加上進位如有進位即不為0即繼續加進位 直到為零
想看二進位結果可使用mynumber.toString(2)
(數字轉二進位)parseInt(mybinary,2)
(二進位轉數字)